#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
//class UnusualAdd {
//public:
//    class test {
//    public:
//        friend class UnusualAdd;
//        test() {
//            cnt++;
//        }
//        static int cnt;
//    };
//    int test::cnt = 0;
//    int addAB(int A, int B) {
//        auto ptr = new test[A];
//        auto ptr1 = new test[B];
//        return test::cnt;
//    }
//};
class LCA
{
public:
    int getLCA(int a, int b)
    {
        vector<int> pathA, pathB;
        dfs(1, a, pathA);
        dfs(1, b, pathB);
        int pa = pathA.size() - 1, pb = pathB.size() - 1;
        int gap = abs(pa - pb);
        if (pa > pb)
        {
            pa -= gap;
            while (pathA[pa] != pathB[pb])
            {
                pa--;pb--;
            }
            return pathA[pa];
        }
        else
        {
            pb -= gap;
            while (pathA[pa] != pathB[pb])
            {
                pa--;pb--;
            }
            return pathA[pa];
        }

    }
    bool dfs(int root, int tar, vector<int>& path)
    {
        if (root > tar)    return false;
        if (root == tar)
        {
            path.push_back(root);
            return true;
        }
        path.push_back(root);
        if (!dfs(root * 2, tar, path) && !dfs(root * 2 + 1, tar, path))
        {
            path.pop_back();
            return false;
        }
        return true;
    }
};
class Solution5
{
public:
    int longestSubsequence(vector<int>& arr, int difference)
    {
        int n = arr.size();
        vector<int> f(n, 1), g(n, 1);
        int Max = 1;
        for (int i = 1;i < n;i++)
        {
            for (int j = 0;j < i;j++)
            {
                if (arr[i] == arr[j] + difference)
                {
                    f[i] = max(f[j] + 1, f[i]);
                }
                else if (arr[i] == arr[j] - difference)
                {
                    g[i] = max(g[j] + 1, g[i]);
                }
            }
            Max = max(max(f[i], g[i]),Max);
        }
        return Max;
    }

};
//class Solution66
//{
//public:
//    int longestArithSeqLength(vector<int>& nums)
//    {
//        int n = nums.size(), ret = 2;
//        vector<vector<int>> dp(n, vector<int>(n, 2));
//        unordered_map<int, int> hash;
//        hash[nums[0]] = 0;hash[nums[1]] = 1;
//        for (int i = 2;i < n;i++)
//        {
//            for (int j = 1;j < i;j++)
//            {
//                if (hash.count(2 * nums[j] - nums[i]) && hash[2 * nums[j] - nums[i]] < j)
//                {
//                    dp[][i] = dp[hash[2 * nums[j] - nums[i]][j] + 1;
//                }
//                ret = max(ret, dp[j][i]);
//            }
//            hash[nums[i]] = i;
//        }
//        return ret;
//    }
//};
//class Solution
//{
//public:
//    int numberOfArithmeticSlices(vector<int>& nums)
//    {
//        int n = nums.size();
//        if (n < 3) return 0;
//        int ret = 2, cnt = 0;
//        unordered_map<int, int> hash;
//        vector<vector<int>> dp(n, vector<int>(n, 0));
//        hash[nums[0]] = 0;
//        for (int i = 1;i < n - 1;i++)
//        {
//            for (int j = i + 1;j < n;j++)
//            {
//                if (hash.count(2 * nums[i] - nums[j]) && hash[2 * nums[i] - nums[j]] < i)
//                {
//                    dp[i][j] = dp[hash[2 * nums[i] - nums[j]]][i] + 1;
//                    cnt += dp[i][j];
//                }
//            }
//            hash[nums[i]] = i;
//        }
//        return cnt;
//    }
//};
//class Solution
//{
//public:
//    int numberOfArithmeticSlices(vector<int>& nums)
//    {
//        int n = nums.size();
//        if (n < 3) return 0;
//        int cnt = 0;
//        vector<vector<int>> dp(n, vector<int>(n, 0));
//        for (int i = 1;i < n - 1;i++)
//        {
//            for (int j = i + 1;j < n;j++)
//            {
//                for (int k = 0;k < i;k++)
//                {
//                    if ((long double)nums[k] / 2 + (long double)nums[j] / 2 == nums[i])
//                    {
//                        dp[i][j] += dp[k][i]+1;
//                    }
//                }
//                cnt += dp[i][j];
//            }
//        }
//        return cnt;
//    }
//};
class Solution
{
public:
    int numberOfArithmeticSlices(vector<int>& nums)
    {
        int n = nums.size();
        if (n < 3) return 0;
        int cnt = 0;
        unordered_map<int, vector<int>> hash;
        hash[nums[0]].push_back(0);
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = 1;i < n - 1;i++)
        {
            for (int j = i + 1;j < n;j++)
            {
                if (hash.count(2 * (long double)nums[i] - nums[j]))
                {
                    for (auto e : hash[(2 * (long double)nums[i] - nums[j])])
                    {
                        dp[i][j] = dp[e][i] + 1;
                    }
                }
                cnt += dp[i][j];
            }
            hash[nums[i]].push_back(i);
        }
        return cnt;
    }
};
int main()
{
   /* LCA().getLCA(2, 4);*/
    vector<int> v = { 7,7,7,7 };
    Solution().numberOfArithmeticSlices(v);
	return 0;
}